#pragma once
#include <sstream>
#include <string>
#include "Node.h"
using namespace std;

/**
*	An implementation of a single-linked list without sorting.
*	
*	The class contains one pointer to a node-object named the "head" of the list and
*	one named the "tail" of the list.
*/

template < class T >
class ContainerList
{

	/**
	*	The class has an iterator implemented to make traversing the list a little bit less painful.
	*/
	class Iterator
	{
	public:
		typedef Iterator self_type;
		typedef Node<T> value_type;
		typedef Node<T>& reference;
		typedef Node<T>* pointer;
		typedef std::forward_iterator_tag iterator_category;
		typedef int difference_type;
		
		Iterator(pointer ptr) : ptr_(ptr) { } //Constructor
		self_type operator++() { self_type i = *this; ptr_=ptr_->next; return i; }
		self_type operator++(int junk) { ptr_=ptr_->next; return *this; }
		reference operator*() { return *ptr_; }
		pointer operator->() { return ptr_; }
		bool operator==(const self_type& rhs) { return ptr_ == rhs.ptr_; }
		bool operator!=(const self_type& rhs) { return ptr_ != rhs.ptr_; }
		
	private:
		pointer ptr_;
	};
private:
	Node<T> *head;
	Node<T> *tail;

public:

	/**
	*	The basic constructor sets both the head and the tail pointer to nullptr, indicating an empty list.
	*/
	ContainerList(void)
	{
		head = tail = nullptr;
	}

	/**
	*	The basic destructor makes sure that all the nodes in the list is deleted from memory before terminating.
	*/
	~ContainerList(void)
	{
		Node<T> *n = head;
		Node<T> *d = n;

		while( n != nullptr )
		{
			d = n;
			n = n->next;
			delete d;
		}
	}

	/**
	*	The str() function basically returns a string with all the info from each node currently in the list.
	*/
	string str()
	{
		ostringstream oss;
		Node<T> *n = head;

		while( n != nullptr )
		{
			oss << n->info << " ";
			n = n->next;
		}

		return oss.str();
	}

	/**
	*	The Add( T info ) function takes info and creates a new Node on the heap, and links it in to the list. 
	*	The function adds new nodes at the head at all times. 
	*/
	void Add( T info )
	{
		if( head == nullptr ) // Empty List
			head = tail = new Node<T>( info );
		else
		{
			Node<T> *n = new Node<T>( info );
			n->next = head;
			head = n;
		}
	}

	/**
	*	The AddUnique( T info ) function takes info and creates a new Node on the heap, and links it in to the list. 
	*	The function adds new nodes at the head at all times.
	*	If the info sent into the function already exists in the list, no new node is added. 
	*/
	void AddUnique( T info )
	{
		if( head == nullptr ) // Empty List
			head = tail = new Node<T>( info );
		else
		{
			Node<T> *s = Search(info);
			if( s == nullptr ) // Info doesn't exist
			{
				Node<T> *n = new Node<T>( info );
				n->next = head;
				head = n;
			}
		}
	}

	/**
	*	The Search( T info ) function lets a user search for a specific info amongst all the nodes in the list.
	*	First it checks to see if the list is empty and if so, returns nullptr. 
	*	If the info is found in a node, a pointer to said node will be returned from the function
	*/
	Node<T> * Search( T info )
	{
		Node<T> *n = head;
		while( n != nullptr )
		{
			if( n->info == info )
				return n;
			n = n->next;
		}
		return nullptr;
	}

	/**
	*	Basically a searchfunction that takes an actual node as parameter.
	*	The function traverses the list and checks if a node's "next"-pointer points to the actual node from the parameter list.
	*	If a match is found, the node is returned as the node before the actual node.
	*/
	Node<T> * NodeBefore( Node<T> *actual )
	{
		Node<T> *n = head;
		while( n != nullptr )
		{
			if( n->next == actual )
				return n;
			n = n->next;
		}
		return nullptr;
	}

	/**
	*	Takes a node to remove from the list.
	*	The functions starts by checking if the list is empty, and then does nothing.
	*	Then it checks if there is only one node in the list and deletes that node
	*	Then checks for the last two special cases, first and last node in list is the one to be deleted.
	*	Standard case is everything else. 
	*	The function makes use of the NodeBefore() function to find node before the one to be deleted in order to be able to make new links with the "next"-pointers.
	*/

	void Remove( Node<T> *d )
	{
		Node<T> *b = nullptr;

		if( d == nullptr || head == nullptr )
			return;
		else if( d == head && head == tail ) // One node in list
		{
			delete d;
			head = tail = nullptr; // now empty list
		}
		else if( d == head ) // Remove first node
		{
			head = head->next;
			delete d;
		}
		else if( d == tail ) // Remove Last node
		{
			b = NodeBefore(d);
			b->next = nullptr;
			tail = b;
			delete d;
		}
		else
		{
			b = NodeBefore(d);
			b->next = d->next;
			delete d;
		}
	}

	Iterator begin()
	{
		return Iterator(head);
	}

	Iterator end()
	{
		return Iterator(nullptr);
	}
};

